<?php


namespace XiaoGuai\DataStructure\LineList\LinkedList;


use XiaoGuai\DataStructure\LineList\ListInterface;
use XiaoGuai\DataStructure\LineList\LinkedList\LinkedListNode as Node;

/**
 * 线性表的链式存储表示
 * Class LinkedList
 * @package XiaoGuai\DataStructure\LineList\LinkedList
 */
class LinkedList implements ListInterface
{
    /**
     * @var null|Node 头指针
     */
    protected $head = null;

    /**
     * 初始化, 创建一个结点, 头指针指向结点(头结点)
     * LinkedList constructor.
     */
    public function __construct()
    {
        $node = new Node();
        $node->next = null;
        $this->head = $node;
    }


    /**
     * 判断线性表是否为空
     * @return bool
     */
    public function isEmpty(): bool
    {
        return $this->head->next == null ? true : false;
    }

    /**
     * 清空线性表,将线性表的数据初始化
     */
    public function clear()
    {
        $node = new Node();
        $node->next = null;
        $this->head = $node;
    }

    /**
     * 返回线性表当前的元素个数
     * @return int
     */
    public function getLength(): int
    {
        $length = 0;

        $p = $this->head->next;
        while ($p) {
            $length++;
            $p = $p->next;
        }

        return $length;
    }

    /**
     * 根据索引获取元素
     * @param int $index
     * @return mixed
     */
    public function getElement(int $index)
    {
        $i = 0;

        $p = $this->head->next;
        while ($p && $i < $index) {
            $p = $p->next; // 依次遍历元素
            $i++;
        }

        if ($p && $i <= $index) {
            return $p->data;
        }

        throw new \Exception('overflow');
    }

    /**
     * 查找元素的索引位置
     * @return int
     */
    public function getIndex($element): int
    {
        $index = -1;

        $p = $this->head->next;
        while ($p) {
            $index++;
            if ($p->data == $element) {
                break;
            }
            $p = $p->next; // 依次遍历元素
        }

        return $p ? $index : -1;
    }

    /**
     * 在对应索引处前面插入数据元素
     * @param int $index
     * @param $element
     * @return bool
     */
    public function insertElement(int $index, $element): bool
    {
        // 查找插入的前一个结点
        $i = 0;

        $p = $this->head->next;
        while ($p && ($i + 1) < $index) {
            $i++;
            $p = $p->next; // 依次遍历元素
        }
        if (!$p || ($i + 1) > $index) {
            return false;
        }

        // 创建结点
        $node = new Node();
        $node->data = $element;

        // 开始插入
        $node->next = $p->next;
        $p->next = $node;

        return true;
    }

    /**
     * 删除对应索引位置的元素
     * @param int $index
     * @return bool
     */
    public function deleteElement(int $index): bool
    {
        // 查找删除的前一个结点
        $i = 0;

        $p = $this->head->next;
        while ($p && ($i + 1) < $index) {
            $i++;
            $p = $p->next; // 依次遍历元素
        }
        if (!$p || ($i + 1) > $index) {
            return false;
        }

        // 开始删除
        $q = $p->next;
        $p->next = $q->next;
        unset($q);

        return true;
    }
}